package LC;

/**
 * https://leetcode.com/problems/search-in-rotated-sorted-array/description/
 * Suppose an array sorted in ascending order
 * is rotated at some pivot unknown to you beforehand.
 * (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
 * You are given a target value to search.
 * If found in the array return its index, otherwise return -1.
 * You may assume no duplicate exists in the array.
 */
public class LC_033_SearchinRotatedSortednumsrray_TwoPointers_BinarySearch {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, -9, -8, -7, -6};
        int idx = Solution.search(a, -9);
        System.out.println(idx);
    }

    static class Solution {
        public static int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;

            while (left <= right) {
                int mid = (left + right) / 2;

                if (nums[mid] == target)
                    return mid;

                if (nums[left] <= nums[mid]) {
                    if (target >= nums[left] && target <= nums[mid])
                        right = mid - 1;
                    else
                        left = mid + 1;
                } else {
                    if (target >= nums[mid] && target <= nums[right])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
            }

            return -1;
        }
    }
}
